/*
 * @lc app=leetcode.cn id=1031 lang=cpp
 *
 * [1031] 两个非重叠子数组的最大和
 */

// @lc code=start
class Solution
{
public:
    int maxSumTwoNoOverlap(vector<int> &nums, int firstLen, int secondLen)
    {
        int n = nums.size();
        vector<int> fmax(n + 1, 0);
        vector<int> smax(n + 1, 0);
        for (int i = n - 1, fsum = 0, ssum = 0; i >= 0; i--)
        {
            fsum += nums[i];
            ssum += nums[i];
            if (i + firstLen < n)
                fsum -= nums[i + firstLen];
            if (i + secondLen < n)
                ssum -= nums[i + secondLen];
            if (i + firstLen <= n)
                fmax[i] = max(fmax[i + 1], fsum);
            if (i + secondLen <= n)
                smax[i] = max(smax[i + 1], ssum);
        }

        int ans = 0;
        for (int i = 0, fsum = 0, ssum = 0; i < n; i++)
        {
            fsum += nums[i];
            ssum += nums[i];
            if (i >= firstLen)
                fsum -= nums[i - firstLen];
            if (i >= secondLen)
                ssum -= nums[i - secondLen];

            ans = max(ans, fsum + smax[i + 1]);
            ans = max(ans, ssum + fmax[i + 1]);
        }

        return ans;
    }
};
// @lc code=end
